package org.example.DataStructure.LinkList;

//利用快慢指针判断单向链表是否有环
public class isCircle {
    public static void main(String[] args) {
        //构建链表数据
        Node<Integer> Node1 = new Node<>(1);
        Node<Integer> Node2 = new Node<>(2);
        Node<Integer> Node3 = new Node<>(3);
        Node<Integer> Node4 = new Node<>(4);
        Node<Integer> Node5 = new Node<>(5);
        Node<Integer> Node6 = new Node<>(6);

        //构建链表指针
        Node1.next = Node2;
        Node2.next = Node3;
        Node3.next = Node4;
        Node4.next = Node5;
        Node5.next = Node6;
        //构建环
        Node6.next = Node3;

        //测试判断有没有环的方法
        System.out.println(isCircle(Node1));

        //测试寻找链表环入口的方法
        System.out.println(getEntrance(Node1));
    }

    //创建节点内部类
    private static class Node<T> {
        //数据域
        T data;
        //指针域
        Node<T> next;

        //构造方法
        public Node(T data) {
            this.data = data;
            this.next = null;
        }
    }

    //利用快慢指针判断链表有没有环的方法
    private static <T> boolean isCircle(Node<T> head) {
        //定义快慢指针
        Node<T> slow = head;
        Node<T> fast = head;
        //遍历链表
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow.equals(fast)) {
                return true;
            }
        }
        //如果没有环
        return false;
    }

    //利用快慢指针找到单项链表环的入口的方法
    //快慢指针相遇的时候将快指针回到链表头节点并设置速度为1，当快慢指针再次相遇的时候就是单向链表环的起点
    private static <T> T getEntrance(Node<T> head) {
        //定义快慢指针
        Node<T> slow = head;
        Node<T> fast = head;
        //遍历链表直到快慢指针相遇
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow.equals(fast)) {
                break;
            }
        }
        //将快指针回溯到链表头节点
        fast = head;
        //再次让快慢指针相遇
        while (!slow.equals(fast)) {
            slow = slow.next;
            fast = fast.next;
        }
        //返回链表环的入口的数据
        return slow.data;
    }
}
